﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using DTO;

namespace BLL
{
    public class VariableNeighborHoodSearch
    {
        private void copyArray(int[] sourceArr, int[] desArray, int numElement)
        {
            for (int i = 0; i < numElement; i++)
            {
                desArray[i] = sourceArr[i];
            }
        }
        
        #region 2-Opt Neighborhood

        //Definition Neighborhood: N_k(x) is the set of solutions having k edges different from x
        public bool checkNeighborhood(PathTour tour_x, int edges_k, PathTour tour_y)
        {
            int numCity = tour_x.OrderCity.Length;
            int countDiff = 0;
            for (int i = 0; i < numCity; i++)
            {
                //posAdj = (i + 2) % numCity;
                if (!((tour_x.OrderCity[i] == tour_y.OrderCity[i]) && (tour_x.OrderCity[i + 1] == tour_y.OrderCity[i + 1])))
                {
                    countDiff++;
                    if (countDiff > edges_k)
                    {
                        return false;
                    }
                }
            }
            if (countDiff == edges_k)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //k-opt (k=2)
        public void k_opt(ref PathTour startTour, CityObject[] citiesCoor)
        {
            int numCity = startTour.OrderCity.Length;
            PathTour tempTour = startTour;

            Evaluate eval = new Evaluate();
            for (int i = 0; i < numCity; i++)
            {
                for (int j = i + 2; j < numCity; j++)
                {
                    int tempCity = tempTour.OrderCity[(i + 1) % numCity];
                    tempTour.OrderCity[(i + 1) % numCity] = tempTour.OrderCity[j];
                    tempTour.OrderCity[j] = tempCity;
                    tempTour.Fitness = eval.calCostOfTour(tempTour.OrderCity, numCity, citiesCoor);
                    if (tempTour.Fitness < startTour.Fitness)
                    {
                        startTour = tempTour;//??????/
                        return;
                    }
                }
            }


        }

        /**
	     * This method implements the 2-opt with fixed edge removal.
	     * For random generation of any of the two edges, one must assign it with a negative number.
	     * @param parents the list of parents. For the 2-opt operation, only one parent is needed.
	     * @param k1 the first edge to be removed. If it is a negative number, a random number will be assigned.
	     * @param k2 the second edge to be removed. If it is a negative number, a random number will be assigned.
	     * @return the child route.
	     */
        public int[] twoSwap(int[] startTour, int k1, int k2, Random ran)
        {
            int edge1;
            int edge2;
            int numCity = startTour.Length;
            do
            {
                edge1 = k1 < 0 ? ran.Next(numCity) : k1;
                edge2 = k2 < 0 ? ran.Next(numCity) : k2;

                if (edge1 > edge2)
                {
                    int aux = edge1;
                    edge1 = edge2;
                    edge2 = aux;
                }
            } while (edge1 == edge2);

            int[] child = new int[numCity];
            int i = 0;
            while (i <= edge1)
            {
                child[i] = startTour[i];
                i++;
            }

            int j = edge2;
            while (i < edge2 + 1)
            {
                child[i] = startTour[j];
                i++;
                j--;
            }

            while (i < numCity)
            {
                child[i] = startTour[i];
                i++;
            }
            return child;
        }

        //create random neighborhood k_th use 2-opt swap neighborhood
        public int[] get2OptNeighborhood(PathTour solution, int k_Neighborhood, Random ran)
        {
            int[] tour1 = new int[solution.OrderCity.Length];
            int[] tour2 = new int[solution.OrderCity.Length];
            copyArray(solution.OrderCity, tour1, solution.OrderCity.Length);

            for (int i = 0; i < k_Neighborhood; i++)
            {
                tour2 = twoSwap(tour1, -1, -1, ran);
                copyArray(tour2, tour1, tour2.Length);
            }
            return tour2;
        }

        //2-opt: reverse segment between two point
        public PathTour twoOptHeuristic(PathTour startTour, ref PathTour bTour, CityObject[] cities, Random ran)
        {
            int numCity = startTour.OrderCity.Length;
            double cost1, cost2;
            Evaluate eval = new Evaluate();

            int[] tempTour = new int[numCity];
            int[] bestTour = new int[numCity];

            PathTour optTour = new PathTour(numCity);
            copyArray(startTour.OrderCity, bestTour, numCity);

            exitFor:
            copyArray(bestTour, tempTour, numCity);
            for (int i = 0; i < numCity; i++)
            {
                for (int j = i + 2; j < numCity; j++)
                {
                    cost1 = cost2 = 0;
                    cost1 = eval.calculateDistance(tempTour[i % numCity] - 1, tempTour[(i + 1) % numCity] - 1, cities) +
                        eval.calculateDistance(tempTour[j % numCity] - 1, tempTour[(j + 1) % numCity] - 1, cities);
                    cost2 = eval.calculateDistance(tempTour[i % numCity] - 1, tempTour[j % numCity] - 1, cities) +
                        eval.calculateDistance(tempTour[(i + 1) % numCity] - 1, tempTour[(j + 1) % numCity] - 1, cities);
                    if (cost2 < cost1)
                    {
                        bestTour = twoSwap(tempTour, i, j, ran);
                        goto exitFor;
                    }
                }
            }
            copyArray(bestTour, optTour.OrderCity, numCity);
            //optTour = (PathTour)bestTour.Clone();
            eval.calculateFitness(ref optTour, ref bTour, numCity, cities);
            return optTour;
        }//two-opt heuristic

        //Variable Neighborhood Search
        public PathTour VNS(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = x_tour.OrderCity.Length;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = get2OptNeighborhood(currentTour, k, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;

            } while (k <= kmax);
            return currentTour;
        }
        
        //VNS: dung khi tim duoc tour tot hon hoac qua so lan danh gia hoac dat toi lan can Kmax
        //Variable Neighborhood Search
        public PathTour VNS_2Opt(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = x_tour.OrderCity.Length;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);
                
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = get2OptNeighborhood(currentTour, k, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {                          
                    currentTour = (PathTour)xxx_tour.Clone();
                    return currentTour;
                }
                else
                {
                    k++;
                }
                countEvaluate++;

            } while (k <= kmax);
            return currentTour;
        }
      
        #endregion

        #region Swap Neighborhood
        public int[] swapCities(int[] sTour, Random ran)
        {
            int[] tempTour = new int[sTour.Length];
            int pos1, pos2;
            do
            {
                pos1 = ran.Next(sTour.Length);
                pos2 = ran.Next(sTour.Length);

                if (pos1 > pos2)
                {
                    int aux = pos1;
                    pos1 = pos2;
                    pos2 = aux;
                }
            } while (pos1 == pos2);
            for (int i = 0; i < pos1; i++)
            {
                tempTour[i] = sTour[i];
            }
            tempTour[pos1] = sTour[pos2];
            for (int i = pos1 + 1; i < pos2; i++)
            {
                tempTour[i] = sTour[i];
            }
            tempTour[pos2] = sTour[pos1];
            for (int i = pos2 + 1; i < sTour.Length; i++)
            {
                tempTour[i] = sTour[i];
            }
            return tempTour;
        }

        public int[] swapNeighborhood(PathTour sTour, int k_Neighborhood, Random ran)
        {
            int[] tour1 = new int[sTour.OrderCity.Length];
            int[] tour2 = new int[sTour.OrderCity.Length];
            copyArray(sTour.OrderCity, tour1, sTour.OrderCity.Length);

            for (int i = 0; i < k_Neighborhood; i++)
            {
                tour2 = swapCities(tour1, ran);
                copyArray(tour2, tour1, tour2.Length);
            }
            return tour2;
        }

        //VNS using swap neighborhood -> Dung voi GA rieng
        public PathTour VNS_swap_Neighborhood(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = x_tour.OrderCity.Length;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                xx_tour.OrderCity = swapNeighborhood(currentTour, k, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
            } while (k <= kmax);
            return currentTour;
        }

        //VNS: dung khi tim duoc tour tot hon hoac qua so lan danh gia hoac dat toi lan can Kmax -> Dung ket hop voi GA
        public PathTour VNS_SwapNeighborhood(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k = 1;
            int kmax = x_tour.OrderCity.Length;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapNeighborhood(currentTour, k, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                countEvaluate++;
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    return currentTour;
                }
                else
                {
                    k++;
                }
            } while (k <= kmax);
            return currentTour;
        }
        

        #endregion
  
        #region Insert Neighborhood
        /*
        *Insertion neighborhood includes all the tours that can be obtained from the given one by removing a vertex and inserting 
        *it at some other position. It can be viewed as a special case of 3opt
        */
        public int[] insertCity(int[] sTour, Random ran)
        {
            int[] tempTour = new int[sTour.Length];
            int pos1, pos2;
            do
            {
                pos1 = ran.Next(sTour.Length);
                pos2 = ran.Next(sTour.Length);

                if (pos1 > pos2)
                {
                    int aux = pos1;
                    pos1 = pos2;
                    pos2 = aux;
                }
            } while (pos1 == pos2);

            for (int i = 0; i < pos1; i++)
            {
                tempTour[i] = sTour[i];
            }
            tempTour[pos1] = sTour[pos2];
            for (int i = pos1 + 1; i <= pos2; i++)
            {
                tempTour[i] = sTour[i - 1];
            }
            for (int i = pos2 + 1; i < sTour.Length; i++)
            {
                tempTour[i] = sTour[i];
            }
            return tempTour;
        }

        public int[] insertNeighborhood(PathTour sTour, int k_Neighborhood, Random ran)
        {
            int[] tour1 = new int[sTour.OrderCity.Length];
            int[] tour2 = new int[sTour.OrderCity.Length];
            copyArray(sTour.OrderCity, tour1, sTour.OrderCity.Length);

            for (int i = 0; i < k_Neighborhood; i++)
            {
                tour2 = insertCity(tour1, ran);
                copyArray(tour2, tour1, tour2.Length);
            }
            return tour2;
        }

        //VNS using insert neighborhood
        public PathTour VNS_Insert_Neighborhood(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = x_tour.OrderCity.Length;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = insertNeighborhood(currentTour, k, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;
            } while (k <= kmax);
            return currentTour;
        }                

        #endregion      

        #region Random Neighborhood
        /************************************************************************/
        /* Neighborhood k is select random k + 1 position from begin chromo     */
        /* k_Neighborhood is less than number of cities                         */
        /************************************************************************/
        public int[] randomSegmentNeighborhood(PathTour sTour, int k_Neighborhood, Random ran)
        {
            int[] tour = new int[sTour.OrderCity.Length];
            if (k_Neighborhood == 1)
            {
                copyArray(sTour.OrderCity, tour, sTour.OrderCity.Length);
                int tempCt = tour[1];
                tour[1] = tour[0];
                tour[0] = tempCt;
            }
            else
            {
                int[] tour1 = new int[k_Neighborhood + 1];
                int pos, numElement;
                for (int i = 0; i < k_Neighborhood + 1; i++)
                {
                    tour1[i] = sTour.OrderCity[i];
                }
                numElement = k_Neighborhood + 1;
                for (int i = 0; i < k_Neighborhood - 1; i++)
                {
                    pos = ran.Next(numElement);
                    tour[i] = tour1[pos];
                    for (int j = pos; j < numElement - 1; j++)
                    {
                        tour1[j] = tour1[j + 1];
                    }
                    numElement--;
                }
                tour[k_Neighborhood - 1] = tour1[1];
                tour[k_Neighborhood] = tour1[0];
                for (int i = k_Neighborhood + 1; i < sTour.OrderCity.Length; i++)
                {
                    tour[i] = sTour.OrderCity[i];
                }
            }
            return tour;
        }

        public PathTour VNS_randomSegment_Neighborhood(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = x_tour.OrderCity.Length;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                xx_tour.OrderCity = randomSegmentNeighborhood(currentTour, k, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
            } while (k < kmax);
            return currentTour;
        }
        
        #endregion
               
        #region swapInSegment
        /********************************************************************************/
        /* Chia Tour lam m=kmax=ncity/10 doan                                           */
        /* Nk duoc thuc hien boi doi vi tri 2 thanh pho ke nhau trong cac doan tu 1..k  */
        /********************************************************************************/
        public int[] swapInSegment(PathTour sTour, int k_Neighbourhood, int sgm_Length, Random ran)
        {
            int[] tour = new int[sTour.OrderCity.Length];
            copyArray(sTour.OrderCity, tour, sTour.OrderCity.Length);
            int pos, temp;
            for (int i = 0; i < k_Neighbourhood; i++)
            {
                pos = ran.Next(sgm_Length - 1);
                temp = tour[i * sgm_Length + pos];
                tour[i * sgm_Length + pos] = tour[i * sgm_Length + pos + 1];
                tour[i * sgm_Length + pos + 1] = temp;
            }
            return tour;
        }

        //VNS: dung khi qua so lan danh gia hoac dat toi lan can Kmax
        public PathTour VNS_SwapInSegment(PathTour x_tour, int k_max, int sgm_Length, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
           
            int k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);
         
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapInSegment(currentTour, k, sgm_Length, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();                  
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;           
            } while (k <= k_max);
            return currentTour;
        }

        //VNS: dừng khi tim duoc tour tot hon hoac qua so lan danh gia hoac dat toi lan can Kmax
        public PathTour VNS_SwapInSegment_1(PathTour x_tour, int k_max, int sgm_Length, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapInSegment(currentTour, k, sgm_Length, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                countEvaluate++;
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    return currentTour;
                }
                else
                {
                    k++;
                }               
            } while (k <= k_max);
            return currentTour;
        }
        
        //VNS voi 1 tour ngau nhien
        public PathTour VNS_Alg_SwapInSegment(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, int numSgm, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = numSgm;
            int sgmLength = x_tour.OrderCity.Length / numSgm;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapInSegment(currentTour, k, sgmLength, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;

            } while (k <= kmax);
            return currentTour;
        }

        #endregion
    
        #region InSegment
        /****************************************************************************/
        /* Chia Tour lam m=kmax=ncity/10 doan                                       */
        /* Nk duoc thuc hien boi: lam dao lon vi tri cac thanh pho trong doan 1..k  */
        /****************************************************************************/
        public int[] Segment(PathTour sTour, int k_Neighbourhood, int sgm_Length, Random ran)
        {
            int[] tour = new int[sTour.OrderCity.Length];
            copyArray(sTour.OrderCity, tour, sTour.OrderCity.Length);
            int pos1, pos2, temp;
            for (int i = 0; i < k_Neighbourhood; i++)
            {
                for (int j = 0; j < sgm_Length; j++)
                {
                    pos1 = ran.Next(sgm_Length);
                    pos2 = ran.Next(sgm_Length);
                    temp = tour[i * sgm_Length + pos1];
                    tour[i * sgm_Length + pos1] = tour[i * sgm_Length + pos2];
                    tour[i * sgm_Length + pos2] = temp;
                }
            }
            return tour;
        }

        //VNS: dung khi qua so lan danh gia hoac dat toi lan can Kmax
        public PathTour VNS_InSegment(PathTour x_tour, int k_max, int sgm_Length, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);
      
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = Segment(currentTour, k, sgm_Length, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();              
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;              
            } while (k <= k_max);
            return currentTour;
        }

        //VNS: dung khi tim duoc tour tot hon hoac qua so lan danh gia hoac dat toi lan can Kmax
        public PathTour VNS_InSegment_1(PathTour x_tour, int k_max, int sgm_Length, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = Segment(currentTour, k, sgm_Length, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                countEvaluate++;
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    return currentTour;
                }
                else
                {
                    k++;
                }              
            } while (k <= k_max);
            return currentTour;
        }

        //Ap dung rieng VNS cho 1 tour ngau nhien
        public PathTour VNS_Alg_InSegment(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, int numSgm, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = numSgm;
            int sgmLength = x_tour.OrderCity.Length / numSgm;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapInSegment(currentTour, k, sgmLength, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;

            } while (k <= kmax);
            return currentTour;
        }

        #endregion

        #region Move segment
        /****************************************************************************/
        /* Chia Tour lam m=kmax=ncity/10 doan                                       */
        /* Nk duoc thuc hien boi: dao k lan vi tri cua 2 doan (segment)             */
        /****************************************************************************/
        public int[] swapSegment(PathTour sTour, int k_Neighbourhood, int numSgm, Random ran)
        {
            int[] tour = new int[sTour.OrderCity.Length];
            copyArray(sTour.OrderCity, tour, sTour.OrderCity.Length);
            int pos1, pos2, temp;
            int sgmNum1, sgmNum2;
            int sgm_Length = sTour.OrderCity.Length / numSgm;
            int lastSgmLgth = sTour.OrderCity.Length % numSgm + sgm_Length;
            for (int i = 0; i < k_Neighbourhood; i++)
            {
                do
                {
                    sgmNum1 = ran.Next(numSgm);
                    sgmNum2 = ran.Next(numSgm);
                } while (sgmNum1 == sgmNum2);
                //Neu doan thu nhat la doan cuoi cung thi doi gia tri cho doan 2 de 
                if (sgmNum1 == numSgm - 1)
                {
                    temp = sgmNum2;
                    sgmNum2 = sgmNum1;
                    sgmNum1 = temp;
                }

                //Neu doan thu 2 la doan cuoi cung
                if (sgmNum2 == numSgm - 1)
                {
                    int[] lstSgmArr = new int[lastSgmLgth];
                    //Luu doan sgm2 ra mang tam thoi
                    for (int j = 0; j < lastSgmLgth; j++)
                    {
                        lstSgmArr[j] = tour[j + tour.Length - lastSgmLgth];
                    }
                    //Chuyen doan sgm 1 ve vi tri cua sgm2
                    for (int j = 0; j < sgm_Length; j++)
                    {
                        tour[j + tour.Length - sgm_Length] = tour[j + sgmNum1 * sgm_Length];
                    }
                    //Dich chuyen cac doan nam giua sgm1 va sgm2
                    for (int j = tour.Length - sgm_Length - 1; j > (sgmNum1 + 1) * sgm_Length; j--)
                    {
                        tour[j] = tour[j - (lastSgmLgth - sgm_Length)];
                    }
                    //Dien vi tri doan sgm2 vao vi tri sgm1
                    for (int j = 0; j < lastSgmLgth; j++)
                    {
                        tour[j + sgmNum1*sgm_Length] = lstSgmArr[j];
                    }
                }
                else
                {                                        
                    for (int j = 0; j < sgm_Length; j++)
                    {
                        temp = tour[sgmNum1 * sgm_Length + j];
                        tour[sgmNum1 * sgm_Length + j] = tour[sgmNum2 * sgm_Length + j];
                        tour[sgmNum2 * sgm_Length + j] = temp;
                    }                    
                }
            }
            return tour;
        }
        
        //VNS: dung khi tim duoc tour tot hon hoac qua so lan danh gia hoac dat toi lan can Kmax
        public PathTour VNS_SwapSegment(PathTour x_tour, int k_max, int numSgm, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapSegment(currentTour, k, numSgm, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                countEvaluate++;
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    return currentTour;
                }
                else
                {
                    k++;
                }
            } while (k <= k_max);
            return currentTour;
        }
        
        //Ap dung rieng VNS cho 1 tour ngau nhien
        public PathTour VNS_Alg_SwapSegment(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, int numSgm, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = numSgm;         
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapSegment(currentTour, k, numSgm, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;

            } while (k <= kmax);
            return currentTour;
        }
        

        #endregion

        #region SwapSegment + SwapInSegment
        /****************************************************************************************************************/
        /* Chia Tour lam m=kmax=ncity/10 doan                                                                           */
        /* Nk duoc thuc hien boi: dao k lan vi tri cua 2 doan (segment) va trong moi doan se dao lon vi tri ca phan tu  */
        /****************************************************************************************************************/

        //VNS: dung khi tim duoc tour tot hon hoac qua so lan danh gia hoac dat toi lan can Kmax
        public PathTour VNS_CombineSwapAndMoveSegment(PathTour x_tour, int k_max, int numSgm, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);
            int sgm_Length = x_tour.OrderCity.Length / numSgm;

            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }

                xx_tour.OrderCity = Segment(currentTour, k, sgm_Length, ran);
                xx_tour.OrderCity = swapSegment(xx_tour, k, numSgm, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                countEvaluate++;
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    return currentTour;
                }
                else
                {
                    k++;
                }
            } while (k <= k_max);
            return currentTour;
        }

        //Ap dung rieng VNS cho 1 tour ngau nhien
        public PathTour VNS_Alg_CombineSwapAndMoveSegment(PathTour x_tour, CityObject[] citiesCoor, ref PathTour bTour, int numSgm, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k, kmax;
            kmax = numSgm;
            int sgmLength = x_tour.OrderCity.Length / numSgm;
            k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);
            int sgm_Length = x_tour.OrderCity.Length / numSgm;
            //currentTour = x_tour;
            //copyArray(x_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = Segment(currentTour, k, sgm_Length, ran);
                xx_tour.OrderCity = swapSegment(xx_tour, k, numSgm, ran);               
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    //copyArray(xxx_tour.OrderCity, currentTour.OrderCity, x_tour.OrderCity.Length);
                    //currentTour = xxx_tour;
                    k = 1;
                }
                else
                {
                    k++;
                }
                countEvaluate++;

            } while (k <= kmax);
            return currentTour;
        }
    
        #endregion


        #region Doi cho 2 tp ke nhau
        public int[] swapNextCity(int[] sTour, Random ran)
        {
            int[] tempTour = new int[sTour.Length];
            int pos1, pos2, tempCity;
            copyArray(sTour, tempTour, sTour.Length);
            pos1 = ran.Next(sTour.Length);
           
            for (int i = 0; i < pos1; i++)
            {
                tempTour[i] = sTour[i];
            }

            if (pos1 == sTour.Length - 1)
            {
                pos2 = 0;
            }
            else
            {
                pos2 = pos1 + 1;
            }

            tempCity = tempTour[pos1];
            tempTour[pos1] = tempTour[pos2];
            tempTour[pos2] = tempCity;
            return tempTour;
        }

        public int[] swapNextCityNeighborhood(PathTour sTour, int k_Neighborhood, Random ran)
        {
            int[] tour1 = new int[sTour.OrderCity.Length];
            int[] tour2 = new int[sTour.OrderCity.Length];
            copyArray(sTour.OrderCity, tour1, sTour.OrderCity.Length);

            for (int i = 0; i < k_Neighborhood; i++)
            {
                tour2 = swapNextCity(tour1, ran);
                copyArray(tour2, tour1, tour2.Length);
            }
            return tour2;
        }
        
        //VNS: dừng khi tim duoc tour tot hon hoac qua so lan danh gia hoac dat toi lan can Kmax
        public PathTour VNS_swapNextCity(PathTour x_tour, int k_max, CityObject[] citiesCoor, ref PathTour bTour, ref int countEvaluate, int totalEvaluate, Random ran)
        {
            int k = 1;
            PathTour currentTour = new PathTour(x_tour.OrderCity.Length);
            PathTour xx_tour = new PathTour(x_tour.OrderCity.Length);
            PathTour xxx_tour = new PathTour(x_tour.OrderCity.Length);

            currentTour = (PathTour)x_tour.Clone();
            do
            {
                if (countEvaluate > totalEvaluate)
                {
                    break;
                }
                xx_tour.OrderCity = swapNextCityNeighborhood(currentTour, k, ran);
                xxx_tour = twoOptHeuristic(xx_tour, ref bTour, citiesCoor, ran);
                countEvaluate++;
                if (xxx_tour.Fitness < currentTour.Fitness)
                {
                    currentTour = (PathTour)xxx_tour.Clone();
                    return currentTour;
                }
                else
                {
                    k++;
                }
            } while (k <= k_max);
            return currentTour;
        }
        
        #endregion

        #region Thay doi su dung cac lan can cua VNS voi nhau
        //numEval -> Luu so lan danh gia ma fitness cua ca the tot nhat chua thay doi
        //numEval -> Neu sau numEval lan danh gia ma fitness cua ca the tot nhat khong thay doi thi chuyen sang VNS khac
     
        #endregion

    }
}
